package day0312

import . "gocode/algorithm/utils"

var nums []int

func recoverTree(root *TreeNode) {
	nums = make([]int, 0)
	inorderTravel(root)
	i, j := findTwoSwapped()
	recover_(root, nums[i], nums[j])
}

func inorderTravel(root *TreeNode) {
	if root == nil {
		return
	}
	inorderTravel(root.Left)
	nums = append(nums, root.Val)
	inorderTravel(root.Right)
}

func findTwoSwapped() (int, int) {
	index1, index2 := -1, -1
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] > nums[i+1] {
			index2 = i + 1
			if index1 == -1 {
				index1 = i
			} else {
				break
			}
		}
	}
	return index1, index2
}

func recover_(root *TreeNode, x, y int) {
	if root == nil {
		return
	}
	if root.Val == x || root.Val == y {
		if root.Val == x {
			root.Val = y
		} else {
			root.Val = x
		}
	}
	recover_(root.Left, x, y)
	recover_(root.Right, x, y)
}
